// https://leetcode.cn/problems/longest-valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 栈+标记数组法求解最长有效括号子串
// 2. 使用栈匹配括号，标记所有成功匹配的括号位置
// 3. 遍历标记数组，统计连续匹配的最长长度
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <stack>

class Solution 
{
public:
    int longestValidParentheses(string s) 
    {
        int length = s.size();

        stack<int> st;
        vector<bool> isvalid(length, false);

        for (int i = 0 ; i < length ; i++)
        {
            if (s[i] == '(')
            {
                st.push(i);
            }
            else if (s[i] == ')')
            {
                if (st.empty() == false)
                {
                    isvalid[i] = true;
                    int index = st.top();
                    st.pop();
                    isvalid[index] = true;
                }
            }
        }

        int ret = 0, count = 0;
        for (int i = 0 ; i < length ; i++)
        {
            if (isvalid[i] == true)
            {
                count++;
            }
            if (isvalid[i] == false || i == length - 1)
            {
                ret = max(ret, count);
                count = 0;
            }
        }

        return ret;
    }
};

int main()
{
    string s1 = "(()", s2 = ")()())";
    Solution sol;

    cout << sol.longestValidParentheses(s1) << endl;
    cout << sol.longestValidParentheses(s2) << endl;

    return 0;
}